package com.fw.leetcode.tree;

import com.fw.leetcode.LeetCode;

/**
 * 124. Binary Tree Maximum Path Sum
 *
 * A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the
 * sequence has an edge connecting them. A node can only appear in the sequence at most once.
 * Note that the path does not need to pass through the root.
 * The path sum of a path is the sum of the node's values in the path.
 * Given the root of a binary tree, return the maximum path sum of any non-empty path.
 *
 * Example 1:
 *  Input: root = [1,2,3]
 *  Output: 6
 *  Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
 *
 * Example 2:
 *  Input: root = [-10,9,20,null,null,15,7]
 *  Output: 42
 *  Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
 *
 * Constraints:
 *  The number of nodes in the tree is in the range [1, 3 * 10^4].
 *  -1000 <= Node.val <= 1000
 */
public class Num_0124 implements LeetCode {
    private interface Solution extends Tree {
        int maxPathSum(TreeNode root);

        default void assertExpected(Integer[] root, int expected) {
            if (maxPathSum(buildBinaryTree(root)) != expected) {
                maxPathSum(buildBinaryTree(root));
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public int maxPathSum(TreeNode root) { // 递归（归纳策略，难）：时O(N) 空O(N)
            /*
             * 二叉树中最大路径和
             *            -10
             *       9            20
             *    -    -       15    7
             *
             *     a          -3
             *   b   c       -   -
             * 各个节点都计算 maxSum(a) = a + max(maxPathSum(b) + maxPathSum(c), 0)
             * 各个节点都计算 maxPathSum(a) = a + max(max(maxPathSum(b), maxPathSum(c)), 0)
             * 最后求 max(maxSum(i))
             */
            TreeNode tmp = new TreeNode(Integer.MIN_VALUE);
            maxPathSum(root, tmp);
            return tmp.val;
        }

        private int maxPathSum(TreeNode root, TreeNode tmp) { // 左右两边只取一条边的和
            if (root == null) return 0;
            int left = Math.max(maxPathSum(root.left, tmp), 0); // 剪枝小于 0 的子节点
            int right = Math.max(maxPathSum(root.right, tmp), 0);
            int maxSum = root.val + left + right;
            if (maxSum > tmp.val) {
                tmp.val = maxSum;
            }
            return root.val + Math.max(left, right); // 已剪枝小于 0 的子节点
        }
    }

    public static void main(String[] args) {
        Solution solution = new MySolution();
        solution.assertExpected(new Integer[]{-3}, -3);
        solution.assertExpected(new Integer[]{1,2,3}, 6);
        solution.assertExpected(new Integer[]{-10,9,20,null,null,15,7}, 42);
    }
}
